package algs4.sort;

public class Insertion
{
    /* Static Methods */
    public static void sort(Comparable[] a) {
        int n = a.length;

        for (int i = 1; i < n; i++) {
            int        j = i;
            Comparable v = a[i];

            for (; j > 0 && v.compareTo(a[j-1]) < 0; j--)
                a[j] = a[j-1];

            a[j] = v;
        }
    }

    public static void sort(Comparable[] a, int st, int ed) {
        for (int i = st + 1; i <= ed; i++) {
            int        j = i;
            Comparable v = a[i];

            for (; j > st && v.compareTo(a[j-1]) < 0; j--)
                a[j] = a[j-1];

            a[j] = v;
        }
    }
}
